package com.example.demo;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class LCS {

    /**
     * 最长公共子序列
     */
    @Test
    public void test() {
        // ando
        int findLCS = findLCS("android", "random");
        int findLCS2 = findLCS2("android", "random");

        // int findLCS = findLCS("苏EA0R82", "苏DA0R829");
        // int findLCS2 = findLCS2("苏EA0R82", "苏DA0R829");
        // System.out.println("最长公共子序列：" + findLCS);
        System.out.println("最长公共子序列：" + findLCS2);
    }

    // 推荐，相等时，斜对角线+1，不相等时，斜对角线取左和上的最大值
    public int findLCS2(String A, String B) {
        int n = A.length();//android
        int m = B.length();//random
        char[] a = A.toCharArray();
        char[] b = B.toCharArray();
        int[][] dp = new int[n + 1][m + 1];
        System.out.println(Arrays.deepToString(dp));

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i] == b[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }
        return dp[n][m];
    }

    public int findLCS(String A, String B) {
        int n = A.length();//android
        int m = B.length();//random
        char[] a = A.toCharArray();
        char[] b = B.toCharArray();
        int[][] dp = new int[n][m];

        for (int i = 0; i < n; i++) {
            if (a[i] == b[0]) {
                dp[i][0] = 1;// 第0列
                for (int j = i + 1; j < n; j++) {
                    dp[j][0] = 1;
                }
                break;
            }
        }

        for (int i = 0; i < m; i++) {
            if (b[i] == a[0]) {
                dp[0][i] = 1; // 第0行
                for (int j = i + 1; j < m; j++) {
                    dp[0][j] = 1;
                }
                break;
            }
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (a[i] == b[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }

        return dp[n - 1][m - 1];
    }

    @Test
    public void test2() {
        longString("苏EA0R82", "苏DA0R829");
    }

    public static void longString(String s1, String s2) {
        String shortStr = s1.length() < s2.length() ? s1 : s2;
        String longStr = s1.length() > s2.length() ? s1 : s2;

        int shortLen = shortStr.length();
        int maxLen = 0, start = 0;
        for (int i = 0; i < shortLen; i++) {
            // 剪枝，子串长度已经不可能超过maxLen，退出循环
            if (shortLen - i < maxLen) {
                break;
            }
            // 左指针j，右指针k, 右指针逐渐向左逼近
            for (int k = shortLen; k > i; k--) {
                String subStr = shortStr.substring(i, k);
                if (longStr.contains(subStr) && maxLen < subStr.length()) {
                    maxLen = subStr.length();
                    start = i;
                    break;
                }
            }
        }
        System.out.println(shortStr.substring(start, start + maxLen));
    }
}
